package com.lx.algorithm.Tree;

import com.lx.algorithm.heap.Heap;

import java.awt.image.renderable.RenderableImage;
import java.util.ArrayList;

import static com.lx.algorithm.Tree.TreeUtils.generateRandomBST;

/**
 * Description: 给定两个节点找两个节点的最早公共祖先
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-20 13:01:07
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-20     张李鑫                     1.0         1.0 Version
 */
public class FindFather {


    public static class Info1 {
        public boolean hasNodeA;
        public boolean hasNodeB;
        public Node node;

        public Info1(boolean hasNodeA, boolean hasNodeB, Node node) {
            this.hasNodeA = hasNodeA;
            this.hasNodeB = hasNodeB;
            this.node = node;
        }
    }


    public static Node findFather(Node a, Node b, Node head) {
        return process(a, b, head).node;
    }

    public static Info1 process(Node a, Node b, Node head) {
        if (null == head) {
            return new Info1(false, false, null);
        }
        Info1 leftInfo1 = process(a, b, head.left);
        Info1 rightInfo1 = process(a, b, head.right);
        boolean hasNodeA = leftInfo1.hasNodeA || rightInfo1.hasNodeA||head == a;
        boolean hasNodeB = leftInfo1.hasNodeB || rightInfo1.hasNodeB||head == b;
        Node node = leftInfo1.node == null ? rightInfo1.node : leftInfo1.node;
        if (node == null&&hasNodeA&&hasNodeB) {
            node=head;
        }
        return new Info1(hasNodeA, hasNodeB, node);
    }

    public static class Info {
        public boolean findA;
        public boolean findB;
        public Node ans;

        public Info(boolean fA, boolean fB, Node an) {
            findA = fA;
            findB = fB;
            ans = an;
        }
    }

    public static Info process1(Node x, Node a, Node b) {
        if (x == null) {
            return new Info(false, false, null);
        }
        Info leftInfo = process1(x.left, a, b);
        Info rightInfo = process1(x.right, a, b);
        boolean findA = (x == a) || leftInfo.findA || rightInfo.findA;
        boolean findB = (x == b) || leftInfo.findB || rightInfo.findB;
        Node ans = null;
        if (leftInfo.ans != null) {
            ans = leftInfo.ans;
        } else if (rightInfo.ans != null) {
            ans = rightInfo.ans;
        } else {
            if (findA && findB) {
                ans = x;
            }
        }
        return new Info(findA, findB, ans);
    }

    public static Node lowestAncestor2(Node head, Node a, Node b) {
        return process1(head, a, b).ans;
    }

    // for test
    public static void fillPrelist(Node head, ArrayList<Node> arr) {
        if (head == null) {
            return;
        }
        arr.add(head);
        fillPrelist(head.left, arr);
        fillPrelist(head.right, arr);
    }


    public static Node pickRandomOne(Node head) {
        if (head == null) {
            return null;
        }
        ArrayList<Node> arr = new ArrayList<>();
        fillPrelist(head, arr);
        int randomIndex = (int) (Math.random() * arr.size());
        return arr.get(randomIndex);
    }

    public static void main(String[] args) {
        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            Node o1 = pickRandomOne(head);
            Node o2 = pickRandomOne(head);
            if (findFather( o1, o2,head) != lowestAncestor2(head, o1, o2)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }


}
